Let l: V(G) → N be a labeling of the vertices of a graph G by positive integers. Define C(u) = Σl(v) + d(u), where d(u) denotes the degree of u and N(u) denotes the open neighborhood of u. In this paper we introduce a new labeling called d-lucky labeling and study the same as a vertex coloring problem. We define a labeling l as d-lucky if c(u) ≠ c(v), for every pair of adjacent vertices u and v in G. The d-lucky number of a graph G, denoted by η(G), is the least positive k such that G has a d-lucky labeling with {1,2,...,k} as the set of labels. We obtain η(G) = 2 for hypercube network, butterfly network, benes network, mesh network, hypertree and X-tree.
展开▼